package problem105_Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal;

public class MySolution {
	 public class TreeNode {
	      public int val;
	      public TreeNode left;
	      public TreeNode right;
	      public TreeNode(int x) { val = x; }
	      
	      public String toString(){
	    	  return "["+val+":left:"+(left==null?"null":left.toString())+",right:"+(right==null?"null":right.toString())+"]";
	      }
	 }
	
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		return dfs(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
	
	private TreeNode dfs(int[] preorder,int start1,int end1, int[] inorder,int start2,int end2){
		if(start2>end2)
			return null;
		if(start2==end2)
			return new TreeNode(inorder[start2]);
		int inOrderIndex=-1;
		for(int i=start2;i<=end2;i++){
			if(inorder[i]==preorder[start1]){
				inOrderIndex=i;
				break;
			}
		}
		TreeNode root=new TreeNode(inorder[inOrderIndex]);
		TreeNode left=dfs(preorder,start1+1,start1+(inOrderIndex-start2),inorder,start2,inOrderIndex-1);
		TreeNode right=dfs(preorder,start1+(inOrderIndex-start2)+1,end1,inorder,inOrderIndex+1,end2);
		root.left=left;root.right=right;
		return root;
	}
	
	public static void main(String[] args){
		System.out.println(new MySolution().buildTree(new int[]{1,2,4,3,5}, new int[]{1,2,3,4,5}));
	}
}
